package leetcode.l0607;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 *
 * candidates中的数字可以无限制重复被选取

 * @author Retain
 * @date 2021/6/7 14:21
 */
public class Medium_组合总和_39 {

    List<List<Integer>> res = new ArrayList<>();

    public static void main(String[] args) {
        Medium_组合总和_39 p = new Medium_组合总和_39();
        p.combinationSum(new int[]{2,3,5},8);
    }
    /**
     * 很容易看出来使用回溯法，但是之前都是在树上进行，如何在数组上进行值得考虑一下
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> list = new ArrayList<>();
        // 优化：对数组进行排序
        Arrays.sort(candidates);
        backTrack(candidates, target, list);
        System.out.println(res);
        return res;
    }

    public void backTrack(int[] candidates, int target,List<Integer> list) {
        int sum = list.stream().mapToInt(v -> v).sum();
        // 如果加起来值超过target则返回
        if (sum > target) {
            return;
        }
        if (sum == target) {
            // 去除重复，通过排序后查看是否包含，应该有其他更好的方法
            ArrayList<Integer> integers = new ArrayList<>(list);
            Collections.sort(integers);
            if (!res.contains(integers)) {
                res.add(integers);
            }
            return;
        }
        for (int candidate : candidates) {
            // 优化剪枝：如果当前值大于target直接跳过
            if (candidate > target) {
                continue;
            }
            list.add(candidate);
            // 回溯
            backTrack(candidates,target, list);
            list.remove(list.size() - 1);
        }
    }
}
